import sun.font.CreatedFontTracker;

import java.util.ArrayList;
import java.util.List;

public class Solution438 {
    /**
     * 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
     * <p>
     * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
     * <p>
     * 说明：
     * <p>
     * 字母异位词指字母相同，但排列不同的字符串。
     * 不考虑答案输出的顺序。
     * 示例 1:
     * <p>
     * 输入:
     * s: "cbaebabacd" p: "abc"
     * <p>
     * 输出:
     * [0, 6]
     * <p>
     * 解释:
     * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
     * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
     */
    public List<Integer> findAnagrams(String s, String p) {
        char[] arrS = s.toCharArray();
        char[] arrP = p.toCharArray();
        List<Integer> res = new ArrayList<>();
        int[] need = new int[26];
        int[] window = new int[26];
        for (char c : arrP) {
            need[c - 'a'] += 1;
        }
        int l = 0, r = 0;
        while (r < arrS.length) {
            int curr = arrS[r] - 'a';
            r++;
            window[curr] += 1;
            while (window[curr] > need[curr]) {
                int curl = arrS[l] - 'a';
                l++;
                window[curl] -= 1;
            }
            if (r - l == arrP.length) {
                res.add(l);
            }
        }
        return res;
    }
}
